#include <sys/time.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
  vector<int> ret;
  int m = matrix.size();

  if(0==m)
    return  ret;

  int n = matrix.front().size();

  if(0==n)
    return ret;

  if(1==m)
    return matrix.front();
  
  int mat[m][n];
  memset(mat, 1, sizeof(mat) );
  
  int dir=0;
  int i=0;
  int j=0;
  int count=0;
  while(count<m*n)
  {
    count++;
    ret.push_back( matrix.at(i).at(j) );
    mat[i][j] = 0;

    if( (i==m-1&&j==0) || (i==0&&j==n-1) || (i==m-1&&j==n-1) || 
        (dir%4==0&&mat[i][j+1]==0) || (dir%4==1&&mat[i+1][j]==0) ||
        (dir%4==2&&mat[i][j-1]==0) || (dir%4==3&&mat[i-1][j]==0) )
      dir++;

    switch(dir%4)
    {
      case 0:
        j++;
        break;
      case 1:
        i++;
        break;
      case 2:
        j--;
        break;
       case 3:
        i--;
        break;
       default:
        break;
    }

  }


  return ret;


}




int main(int argc, char* argv[]) {

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1, &tz);
  vector<vector<int>> mat1;
  vector<int> tmp1={1,2,3,12,13,23};
  mat1.push_back(tmp1);
  vector<int> tmp2={4};//,5,6,45,46,56};
  //mat1.push_back(tmp2);
  vector<int> tmp3={7};//,8,9,78,79,89};
 // mat1.push_back(tmp3);

  vector<int> ret = spiralOrder( mat1 );
  for(vector<int>::iterator iter = ret.begin(); iter!=ret.end(); ++iter)
    cout << *iter << ",";

  cout<<endl;



  int time2 = gettimeofday(&tv2, &tz);
  cout << "time consuming(local machine/leetcode server):" <<endl
       << "leetcode server time consuming should be less than 500ms" <<endl
       << tv2.tv_usec - tv1.tv_usec 
       << "us/" << 0.11 * ( tv2.tv_usec - tv1.tv_usec )
       << "ms" << endl;



  return 0;
}
